package LRU

import "fmt"

type LRUCache struct {
	cap  int
	hash map[int]*node
	head *node
}

type node struct {
	prev       *node
	next       *node
	key, value int
}

func NewLRUCache(cap int) *LRUCache {
	headNode := &node{}
	headNode.prev = headNode
	headNode.next = headNode //使用环形队列，简化操作
	return &LRUCache{
		hash: make(map[int]*node, cap),
		cap:  cap,
		head: headNode,
	}
}

func (cache *LRUCache) Put(key, value int) {
	if len(cache.hash) == cache.cap {
		delete(cache.hash, cache.head.prev.key)
		cache.head.prev.prev.next = cache.head
		cache.head.prev = cache.head.prev.prev
	}
	cache.hash[key] = &node{
		prev:  cache.head,
		next:  cache.head.next,
		key:   key,
		value: value,
	}
	cache.head.next.prev = cache.hash[key]
	cache.head.next = cache.hash[key]
}

func (cache *LRUCache) Get(key int) int {
	if node, ok := cache.hash[key]; ok {
		node.prev.next = node.next
		node.next.prev = node.prev
		node.prev = cache.head
		node.next = cache.head.next
		node.next.prev = node
		node.prev.next = node
		return node.value
	}
	return -1
}

func (cache *LRUCache) PrintAll() {
	fmt.Println("Hash:")
	for k, v := range cache.hash {
		fmt.Printf("key:%d value:%v", k, v.value)
	}
	fmt.Println()
	fmt.Println("Queue:")
	for tmp, i := cache.head.next, len(cache.hash); i > 0; i-- {
		fmt.Printf("node:%v|", tmp.value)
		tmp = tmp.next
	}
}
